﻿#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX(a, b) (a > b ? a : b)

typedef struct
{
	int money;
	int hard;
}AppropriateJobAndIncomeData;

static int getBestJob(const AppropriateJobAndIncomeData* jobs, const size_t count, const int ability, int index)
{
	if (index > count - 1) return 0;

	int useCurJobIncome = (ability >= jobs[index].hard) ? jobs[index].money : 0;
	int notUseCurJobIncome = getBestJob(jobs, count, ability, index + 1);
	return MAX(useCurJobIncome, notUseCurJobIncome);
}

/**
 * 为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下，
 * 牛牛选择报酬最高的工作。在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作，牛牛依然使用自己的标准来帮助小伙伴们。
 * 但是牛牛的小伙伴太多了，于是他只好把这个任务交给了你。
 *
 * struct Job {
 *     int money; // 该工作的报酬
 *     int hard; // 该工作的难度
 * }
 *
 * 给定一个Job类型的数组jobarr，表示所有的工作。给定一个int类型的数组arr，表示所有小伙伴的能力。
 * 返回int类型的数组，表示每一个小伙伴按照牛牛的标准选工作后所能获得的报酬。
 */
int main_AppropriateJobAndIncome()
{
	AppropriateJobAndIncomeData jobDataArr[] = {
		{1,1},
		{2,3},
		{3,3},
		{4,3},
		{5,4},
		{5,6},
		{7,6},
		{7,8},
		{8,9},
		{10,15},
		{12,15},
		{12,13},
		{15,15},
		{16,20},
	};

	auto jobDataSize = sizeof(jobDataArr) / sizeof(AppropriateJobAndIncomeData);
	int abilities[] = {1,3,5,2,6,7,9,10,18,13};
	int peopleCount = sizeof(abilities) / sizeof(int);

	// 方法1: 暴力递归
	int maxIncome;
	for (int i = 0; i < peopleCount; i++)
	{
		maxIncome = getBestJob(jobDataArr, jobDataSize, abilities[i], 0);
		printf("%d: ability:%d, income:%d\n", i, abilities[i], maxIncome);
	}

	// 方法2: 使用有序表
	map<int, int> maxIncomJobMap;
	map<int, int>::iterator existsPair;
	AppropriateJobAndIncomeData jobData;
	for (int i = 0; i < jobDataSize; i++)
	{
		jobData = jobDataArr[i];
		existsPair = maxIncomJobMap.find(jobData.hard);
		if (existsPair == maxIncomJobMap.end())
		{
			maxIncomJobMap[jobData.hard] = jobData.money;
		}
		else if (existsPair->second < jobData.money)
		{
			maxIncomJobMap[jobData.hard] = jobData.money;
		}
	}

	vector<int> incomes;
	for (int i = 0; i < peopleCount; i++)
	{
		incomes.clear();
		existsPair = maxIncomJobMap.lower_bound(abilities[i]);
		while (existsPair != maxIncomJobMap.end())
		{
			if (existsPair->first <= abilities[i])
			{
				incomes.push_back(existsPair->second);
			}

			--existsPair;
		}

		sort(incomes.begin(), incomes.end(), greater<int>());
		printf("%d: ability:%d, income:%d\n", i, abilities[i], incomes.at(0));
	}

	return 0;
}